package com.cty.A_GeneralDataStructures.B_LinkedList;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/13 17:57
 * @Description: 单向链表
 * 应用场景：
 *      当数据量少时，考虑数组或链表
 *          当数据量不可预测时，考虑链表
 * 重要操作：
 *      ① find(long): DataItem    O(N)
 *      ② insertFirst(DataItem): void    O(1)
 *      ③ insertBefore(long, DataItem): boolean    O(N)
 *      ④ insertAfter(long, DataItem): boolean    O(N)
 *      ⑤ deleteFirst(): DataItem    O(1)
 *      ⑥ delete(): DataItem    O(N)
 *
 * @version: 1.0
 */
public class LinkedList {
    private Node first;

    public LinkedList(){
        first = null;
    }

    public boolean isEmpty(){
        return (first == null);
    }

    public void displayList(){
        Node current = first;
        while(current != null){
            System.out.print(current.data.getKey() + " ");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 查找  O(N)
     * @param key
     * @return
     */
    public DataItem find(long key){
        // 查找
        Node current = first;
        while(current !=null && current.data.getKey()!=key)
            current = current.next;

        // 处理查找结果
        if(current == null)
            return null;  // 不存在关键字为key的节点
        else
            return current.data;  // 返回查找的节点
    }  // end find()

    /**
     * 在表头插入  O(1)
     * @param item
     */
    public void insertFirst(DataItem item){
        Node newNode = new Node(item);
        newNode.next = first;
        first = newNode;
    }

    /**
     * 在指定关键字的节点前面插入  O(N)
     * @param key
     * @param item
     * @return
     */
    public boolean insertBefore(long key, DataItem item){
        if(isEmpty())
            return false;  // 空表

        // 查找
        Node newNode = new Node(item);
        Node current = first;
        Node previous = null;

        while(current!=null && current.data.getKey()!=key){
            previous = current;
            current = current.next;
        }

        // 处理查找结果
        if(current == null)
            return false;  // 不存在关键字为key的节点
        else{
            if(previous == null)  // 表头
                first = newNode;
            else  // 非表头
                previous.next = newNode;
            newNode.next = current;
            return true;  // 插入成功
        }
    }  // end insertBefore()

    /**
     * 在指定关键字的节点后面插入  O(N)
     * @param key
     * @param item
     * @return
     *      true
     *      false——空表或不存在关键字为key的节点
     */
    public boolean insertAfter(long key, DataItem item){
        if(isEmpty())
            return false;  // 空表

        // 查找
        Node newNode = new Node(item);
        Node current = first;

        while(current!=null && current.data.getKey()!=key)
            current = current.next;

        // 处理查找结果
        if(current == null)
            return false;  // 不存在关键字为key的节点
        else{
            newNode.next = current.next;
            current.next = newNode;
            return true;  // 插入成功
        }
    }  // end insertAfter

    /**
     * 在表头删除  O(1)
     * @return
     */
    public DataItem deleteFirst(){
        if(isEmpty())
            return null;

        DataItem temp = first.data;
        first = first.next;
        return temp;
    }

    /**
     * 删除指定关键字的节点  O(N)
     * @param key
     * @return
     */
    public DataItem delete(long key){
        if(isEmpty())
            return null;  // 空表

        // 查找
        Node current = first;
        Node previous = null;

        while(current!=null && current.data.getKey()!=key){
            previous = current;
            current = current.next;
        }

        // 处理查找结果
        if(current == null)
            return null;  // 不存在关键字为key的节点
        else{
            if(previous == null)
                first = current.next;
            else
                previous.next = current.next;
            return current.data;  // 删除成功
        }
    }  // end delete()

    public Node getFirst() {
        return first;
    }

    public void setFirst(Node first) {
        this.first = first;
    }

    public ListIterator getIterator(){
        return new ListIterator(this);
    }
}  // end LinkedList{}
